package com.algorithm.sort;

import com.algorithm.util.RandomUtil;

import java.util.Random;

/**
 * Created by mu on 2018/2/5.
 */
public class Sort {
    public static void main(String[] args) {
        int[] array =/*new int[]{3,2,5,4,8,7,6,9};//*/RandomUtil.randomArray(10000, 0, 10000);
        Sort sort = new Sort();
        //sort.quickSort1(array,0,array.length-1);
        //sort.quickSort2(array,0,array.length-1);
        //sort.quickSort3(array,0,array.length-1);
        //sort.heapSort(array);
        //sort.mergeSort1(array,0,array.length-1);
       // sort.mergeSort2(array,array.length-1);
        //sort.insertSort(array);
        //sort.shellSort(array);
        //sort.selectSort(array);
        sort.bubbleSort(array);
        sort.isSort(array);
        sort.printArray(array);
    }




    public boolean isSort(int[] array) {
        boolean flag=true;
        int i;
        for ( i = 0;i <array.length-1&&(array[i]<=array[i+1]||(flag=false)); i++);
        if(flag==true)
            System.out.println("有序");
        else
            System.out.println("无序");
        return flag;
    }

    /**
     * 打印数组
     * @param array
     */
    public  void printArray(int[] array) {
        for (int i = 0; i <array.length ; i++) {
            System.out.print(array[i]+",");
        }
        System.out.println();
    }

    /**
     * 交换数组两个元素
     * @param arr
     * @param i
     * @param j
     */
    public  void swap(int [] arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    /**普通快排
     *
     * @param array
     * @param low
     * @param high
     */
    public  void quickSort1(int[] array, int low, int high) {
       if(high>low){
           int s=low;
           int fag=low;
           swap(array,s, RandomUtil.randomInt(low,high));
           for(int i=low;i<=high;i++){
               if(array[i]<array[s]){
                   swap(array,i,++fag);
               }
           }
           swap(array,s,fag);
           quickSort1(array,low,fag-1);
           quickSort1(array,fag+1,high);
       }
    }

    /**
     * 双路快排
     * @param array
     * @param low
     * @param high
     */
    public void quickSort2(int[] array, int low, int high) {
        if(high>low){
            int s=low;
            swap(array,s,RandomUtil.randomInt(low,high));
            int i=low,j=high;
            while(j>i){
                for(;i<=high&&array[i]<=array[s];i++);
                for (;j>=low&&array[j]>array[s];j--);
                if(j>i)
                    swap(array,i,j);
            }
            swap(array,s,j);
            quickSort2(array,low,j-1);
            quickSort2(array,j+1,high);
        }
    }

    /**
     * 三路快排
     * @param array
     * @param low
     * @param high
     */
    public void quickSort3(int[] array, int low, int high) {
        if(high>low){
            int before=low,after=high+1;
            int s=low;
            for (int i = low+1; i <after; ) {
                if(array[i]<array[s])
                    swap(array,i++,++before);
                else if(array[i]==array[s])
                    i++;
                else
                    swap(array,--after,i);
            }
            swap(array,s,before);
            quickSort3(array,low,before-1);
            quickSort3(array,before+1,high);
        }
    }

    /**
     * 堆排序
     * @param array
     */
    public void heapSort(int[] array) {
        int n=array.length-1;
        for(int i=(n-1)/2;i>=0;i--){
            heapDown(array,n,i);
        }
        for(int i=n;i>0;i--){
            swap(array,0,i);
            heapDown(array,i-1,0);
        }
    }

    /**
     *堆排序的依赖方法
     */
    private void heapDown(int[] array, int n, int k) {
        while(2*k+1<=n){
            int j=2*k+1;
            if(j+1<=n&&array[j+1]>array[j])
                j++;
            if(array[k]>=array[j])
                break;
            swap(array,k,j);
            k=j;
        }
    }

    /**
     * 递归归并排序，从上到下
     * @param array
     * @param low
     * @param high
     */
    public void mergeSort1(int[] array, int low, int high) {
        if(high>low){
            int mid=(high+low)/2;
            mergeSort1(array,low,mid);
            mergeSort1(array,mid+1,high);
            if(array[mid]>array[mid+1])
                merge(array,low,high);
        }
    }
    public void merge(int array[],int low,int high){
        int mid=(low+high)/2;
        int i=low,j=mid+1,k=0;
        int temp[]=new int[high-low+1];
        while(i<=mid||j<=high){
            if(j>high||(i<=mid&&array[i]<array[j]))
                temp[k++]=array[i++];
            else
                temp[k++]=array[j++];
        }
        for (i = 0; i < k; i++) {
            array[i+low]=temp[i];
        }
    }

    /**
     * 循环递归排序
     *
     * 注意，此方法有问题，没有排到完全有序
     *
     * @param array
     * @param n
     */
    public void mergeSort2(int[] array, int n) {
        for(int i=1;i<=n;i+=i){
            for(int j=0;j+i<n;j+=2*i){
                /*注意，此方法有问题，没有排到完全有序, 若有大佬修改了bug给我说声*/
                merge(array,j,Math.min(n,j+i+i-1));

            }
        }
    }

    /**
     * 插入排序
     * @param array
     */
    public void insertSort(int[] array) {
        int i,j;
        for ( i = 1; i <array.length ; i++) {
            int temp=array[i];
            for( j=i-1;j>=0&&array[j]>temp;array[j+1]=array[j],j--);
            array[j+1]=temp;
        }
    }

    /**
     * 希尔排序
     * @param array
     */
    public void shellSort(int[] array) {
        int n = array.length - 1;
        for(int k=n/2;k>=1;k/=2){
            for(int i=k;i<=n;i+=k){
                int temp=array[i];
                int j;
                for(j=i-k;j>=0&&array[j]>temp;array[j+k]=array[j],j-=k);
                    array[j+k]=temp;
            }
        }
    }

    /**
     * 选择排序
     * @param array
     */
    private void selectSort(int[] array) {
        for(int i=0;i<array.length-1;i++){
            for(int j=i+1;j<array.length;j++){
                if(array[j]<array[i])
                    swap(array,i,j);
            }
        }
    }

    /**
     * 冒泡排序
     * @param array
     */
    private void bubbleSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            boolean flag=true;
            for(int j=0;j<array.length-i-1;j++){
                if (array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flag=false;
                }
            }
            if (flag)
                break;
        }
    }

}
